#include <iostream>
#include <vector>
//#include <algorithm>
using namespace std;

class Sorting {
public:
    // 冒泡排序
    void bubbleSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j + 1]);
                }
            }
        }
    }

    // 选择排序
    void selectionSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr[i], arr[minIndex]);
        }
    }

    // 插入排序
    void insertionSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    //希尔排序
    void shell_sort(vector<int> &arr,int len){
        int h=1;
        while(h<len/3){
            h = 3*h+1;
        }
        while(h>=1){
            for(int i=h;i<len;i++){
                for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h){
                    swap(arr[j],arr[j-h]);
                }
            }
            h=h/3;
        }
    }
    //归并排序
    void merge_sort(vector<int>& arr) {
        int n = arr.size();

        // 子数组大小从1开始，逐渐增加
        for (int curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
            // 左起始索引从0开始，每次移动2倍的子数组大小
            for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
                int mid = min(left_start + curr_size - 1, n - 1);
                int right_end = min(left_start + 2 * curr_size - 1, n - 1);
                merge(arr, left_start, mid, right_end);
            }
        }
    }
    // 快速排序
    void quickSort(vector<int>& arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    // 堆排序
    void heap_sort(vector<int>& arr) {
        int n = arr.size();
        // 建立最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 逐个将最大元素移到数组末尾，并调整堆
        for (int i = n - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            heapify(arr, i, 0);
        }
    }
    //桶排序
//    void bucket_sort(vector<int>& arr) {
//        int n = arr.size();
//        // 创建桶
//        vector<vector<int>> buckets(n);
//        // 将元素分配到不同的桶中
//        for (int i = 0; i < n; i++) {
//            int bucketIndex = n * arr[i];
//            buckets[bucketIndex].push_back(arr[i]);
//        }
//        // 对每个桶中的元素进行排序
//        for (int i = 0; i < n; i++) {
//            sort(buckets[i].begin(), buckets[i].end());
//        }
//        // 合并桶中的元素
//        int index = 0;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < buckets[i].size(); j++) {
//                arr[index++] = buckets[i][j];
//            }
//        }
//    }
    // 基数排序
//    void radix_sort(vector<int>& arr) {
//        int n = arr.size();
//        if (n <= 1) {
//            return;
//        }
//
//        int maxNum = *max_element(arr.begin(), arr.end());  // 获取数组中的最大值
//        // 对每个位数进行计数排序
//        for (int digit = 0; maxNum / digit > 0; digit *= 10) {
//            vector<int> count(10, 0);  // 计数数组，用于统计每个位上的数字出现次数
//            vector<int> output(n);  // 输出数组，保存排序后的结果
//            // 统计每个位上的数字出现次数
//            for (int i = 0; i < n; i++) {
//                int num = getDigit(arr[i], digit);
//                count[num]++;
//            }
//            // 将计数数组进行累加
//            for (int i = 1; i < 10; i++) {
//                count[i] += count[i - 1];
//            }
//
//            // 根据位数进行排序
//            for (int i = n - 1; i >= 0; i--) {
//                int num = getDigit(arr[i], digit);
//                output[count[num] - 1] = arr[i];
//                count[num]--;
//            }
//
//            // 将排序结果复制回原数组
//            for (int i = 0; i < n; i++) {
//                arr[i] = output[i];
//            }
//        }
//    }

    // 排序函数
    void sort_1(vector<int>& arr, string algorithm) {
        if (algorithm == "bubble") {
            bubbleSort(arr);
        } else if (algorithm == "selection") {
            selectionSort(arr);
        } else if (algorithm == "insertion") {
            insertionSort(arr);
        } else if (algorithm == "quick") {
            quickSort(arr, 0, arr.size() - 1);
        } else if (algorithm == "shell") {
            shell_sort(arr,arr.size());
        }else if (algorithm == "merge") {
            merge_sort(arr);
        }else if (algorithm == "heap") {
            heap_sort(arr);
        }else if (algorithm == "bucket") {
            //bucket_sort(arr);
        }else if (algorithm == "radix") {
            //radix_sort(arr);
        }else {
            cout << "Invalid algorithm." << endl;
        }

    }

private:
    // 分区函数（用于快速排序）
    int partition(vector<int>& arr, int low, int high) {
//        int mid = (low+high)/2;
//        int max_low_and_high = max(arr[low],arr[high]);
//        int max_low_and_mid = max(arr[low],arr[high]);
//        int pivot = min(max_low_and_high,max_low_and_mid);
        int pivot = find_pivot(arr,low,high);
        int i = low-1 ;
        int j = high-1;

        while (true) {
            while (arr[++i] < pivot) {
            }

            while (arr[--j] > pivot) {
            }

            if (i >= j) {
                break;
            }

            swap(arr[i], arr[j]);
        }

        swap(arr[high-1], arr[i]);

        return i;
    }
    int find_pivot(vector<int>& arr, int low, int high){//选取最佳主元u，用于快排排序选取主元
        int mid = (low+high)/2;
        if(arr[low]>arr[mid]){
            swap(arr[low],arr[mid]);
        }
        if(arr[low]>arr[high]){
            swap(arr[low],arr[high]);
        }
        if(arr[mid]>arr[high]){
            swap(arr[mid],arr[high]);
        }
        swap(arr[mid],arr[high-1]);
        return arr[high-1];
    }
    // 合并两个有序子数组
    void merge(vector<int>& arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组存储左右子数组
        vector<int> L(n1), R(n2);

        // 将数据复制到临时数组
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // 合并左右子数组到原始数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 处理剩余元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    void heapify(vector<int>& arr, int n, int i) {
        int largest = i;  // 初始化最大元素为根节点
        int left = 2 * i + 1;  // 左子节点索引
        int right = 2 * i + 2;  // 右子节点索引

        // 如果左子节点大于根节点，将最大元素索引更新为左子节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点大于当前最大元素，将最大元素索引更新为右子节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大元素不是根节点，则交换根节点与最大元素，并对交换后的子树进行调整
        if (largest != i) {
            swap(arr[i], arr[largest]);
            heapify(arr, n, largest);
        }
    }
    int getDigit(int num, int digit) {
        int divisor = 1;
        for (int i = 0; i < digit; i++) {
            divisor *= 10;
        }
        return (num / divisor) % 10;
    }

};

